leetcode 31 下一个排列

局部排序。

题目

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

思路

分析下，要找到下一个更大的排序，有两种情况：

第一种，此排列是最大的排列了，这样直接对数组进行升序排序就可以了，输出最小的排列。比如：3 2 1，这样直接排序之后1，2，3

第二种，是中间的某个排列，比如1，2，3，5，4。它的下一个排列应该是1，2，4，3，5。交换的规则如下，要找到下一个更大的排列，原则上来说，需要将一个大的数和前面的一个小的数进行交换，这样就形成了下一个大的排列，例如1，2，3。交换之后变成1，3，2.所以第一步是找到原来排列当中的待交换的那个数，也就是从原来排列的最后一位往前比较，找到小于自身后面的数第一个数，作为待交换的数，因为如果这个数是比后面的数大，那么它往后交换一定是将这个排列变得更小，所以要找到比后面的数小的数作为待交换的数。然后再将待交换的数后面的排列进行升序排序，最后再将待交换的数与后面排序好的序列中的第一个大于自己的数进行交换，这样就得到下一个更大的排序。

code

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if(nums.size()<=1)
            return;
        int l=nums.size()-1;
        for(;l>0;--l)//找到第一个满足条件的交换数。
        {
            if(nums[l]>nums[l-1])
                break;
        }
        if(l==0)//如果l==0，说明是最大排序，直接返回排序结果。
        {
            sort(nums.begin(),nums.end());
        }
        else
        {
            int temp=l-1;
            sort(nums.begin()+l,nums.end());
            for(int i=l;i<nums.size();++i)//因为可能有波峰的情况，所以一定要一个个比对寻找。
            {
                if(nums[temp]<nums[i])
                {
                    l=i;
                    break;
                }
            }
            swap(nums[temp],nums[l]);
        }
        return; 
    }
};